package com.nanbei.sort;

import java.util.Arrays;

/**
 * @ClassDescription: 归并排序（至下而上） 非递归
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/6/26 16:59
 */
public class MergeSortBottomUp {

    public static void main(String[] args) {
        int[] insertion = sort(new int[]{6,3,7,4,5,8,1,2,11,9,10,-1,-3,35});
        System.out.println(Arrays.toString(insertion));
    }

    public static int[] sort(int[] nums) {
        int length = nums.length;
        int[] ints = new int[length];
        //gap 代表区间宽度
        for (int gap = 1; gap <length; gap = gap<<1){
            for (int left = 0; left < length; left = left + gap*2) {
                // 防止右边界超过数组长度
                int right = Math.min(length-1, left + gap*2 -1);
                int mid = Math.min(left+gap-1,length-1);
                merge(nums,left,mid,mid+1,right,ints);
                System.arraycopy(ints,0,nums,left,right-left+1);

            }
        }

        return nums;
    }

    /**
     *
     * @param nums  原始数组
     * @param left  第一个有序数组开始的下标
     * @param leftEnd  第一个有序数组结束的下标
     * @param right 第二个有序数组开始的下标
     * @param rightEnd 第二个有序数组结束的下标
     * @param ints 临时数组
     */
    private static void merge(int[] nums, int left, int leftEnd, int right, int rightEnd, int[] ints) {
        int index = 0;
        while (left <= leftEnd && right <= rightEnd){
            int leftNum = nums[left];
            int rightNum = nums[right];
            if (leftNum < rightNum){
                ints[index++] =leftNum;
                left++;
            }else {
                ints[index++] = rightNum;
                right++;
            }
        }
        if (left <= leftEnd){
            while (left <= leftEnd){
                ints[index++] = nums[left++];
            }
        }
        if (right <= rightEnd){
            while (right <= rightEnd){
                ints[index++] = nums[right++];
            }
        }
    }

}
